package linklist;

/**
 * 自定义链表实现（带头节点的双向链表？不，这里是单向链表，带头节点）
 * 功能：支持增（头插、尾插、指定位置插）、删（指定位置删）、查（按索引查）
 *
 * @author "随风Coding"
 * @email 1431471764@qq.com
 * @date 2025/8/12 16:32
 */
public class MyLinkedList {

    // 链表节点定义（内部类）
    private static class ListNode {
        int val;         // 节点存储的值
        ListNode next;   // 指向下一个节点的指针

        // 构造方法（带值）
        ListNode(int val) {
            this.val = val;
        }
    }

    // 链表实际节点数量（不包含虚拟头节点）
    private int size;
    // 虚拟头节点（辅助插入/删除操作，不存储实际数据）
    private ListNode dummyHead;

    // 初始化链表：创建虚拟头节点，size 初始化为 0
    public MyLinkedList() {
        dummyHead = new ListNode(0); // 虚拟头节点的值无意义（可任意设置）
        size = 0;
    }

    /**
     * 获取链表中第 index 个节点的值（index 从 0 开始，指向实际节点）
     *
     * @param index 目标索引（0 ≤ index < size）
     * @return 节点的值
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    public int get(int index) {
        // 检查索引合法性
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界：index=" + index + ", size=" + size);
        }

        // 从虚拟头节点出发，遍历到目标节点（需移动 index 次）
        ListNode current = dummyHead;
        while (index >= 0) {
            current = current.next; // 移动到下一个节点
            index--;                // 索引递减（剩余移动次数）
        }
        return current.val; // 返回目标节点的值
    }

    /**
     * 在链表头部插入新节点（新节点成为链表的第一个实际节点）
     *
     * @param val 插入节点的值
     */
    public void addHead(int val) {
        // 创建新节点，插入到虚拟头节点之后（成为新的头节点）
        ListNode newNode = new ListNode(val);
        newNode.next = dummyHead.next; // 新节点的 next 指向原头节点
        dummyHead.next = newNode;      // 虚拟头节点的 next 指向新节点
        size++;                        // 实际节点数量加 1
    }

    /**
     * 在链表尾部插入新节点（新节点成为链表的最后一个实际节点）
     *
     * @param val 插入节点的值
     */
    public void addTail(int val) {
        // 创建新节点，遍历到链表末尾（虚拟头节点的最后一个实际节点）
        ListNode newNode = new ListNode(val);
        ListNode current = dummyHead;
        while (current.next != null) { // 找到最后一个实际节点（current.next 为 null）
            current = current.next;
        }
        current.next = newNode; // 将新节点插入到末尾
        size++;                 // 实际节点数量加 1
    }

    /**
     * 在链表的指定索引前插入新节点（index 从 0 开始）
     *
     * @param index 插入位置（0 ≤ index ≤ size）：
     *              - index=0：插入到头部（成为新头节点）
     *              - index=size：插入到尾部（成为新尾节点）
     *              - 0 < index < size：插入到中间
     * @param val   插入节点的值
     * @throws IndexOutOfBoundsException 索引越界时抛出（index < 0 或 index > size）
     */
    public void addAtIndex(int index, int val) {
        // 检查索引合法性（允许 index=size，此时插入到尾部）
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("索引越界：index=" + index + ", size=" + size);
        }

        // 创建新节点，遍历到插入位置的前驱节点（需移动 index 次）
        ListNode newNode = new ListNode(val);
        ListNode current = dummyHead;
        while (index > 0) {
            current = current.next; // 移动到下一个节点
            index--;                // 索引递减（剩余移动次数）
        }
        // 插入新节点：新节点的 next 指向前驱节点的原 next，前驱节点的 next 指向新节点
        newNode.next = current.next;
        current.next = newNode;
        size++; // 实际节点数量加 1
    }

    /**
     * 删除链表中指定索引的节点（index 从 0 开始）
     *
     * @param index 目标索引（0 ≤ index < size）
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    public void deleteAtIndex(int index) {
        // 检查索引合法性
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界：index=" + index + ", size=" + size);
        }

        // 遍历到目标节点的前驱节点（需移动 index 次）
        ListNode current = dummyHead;
        while (index > 0) {
            current = current.next; // 移动到下一个节点
            index--;                // 索引递减（剩余移动次数）
        }

        // 删除目标节点：前驱节点的 next 指向目标节点的 next（跳过目标节点）
        current.next = current.next.next;
        size--; // 实际节点数量减 1
    }

    /**
     * 获取链表的实际节点数量（不包含虚拟头节点）
     *
     * @return 链表长度
     */
    public int getSize() {
        return size;
    }

    /**
     * 打印链表内容（用于测试验证）
     */
    public void printList() {
        ListNode current = dummyHead.next; // 从第一个实际节点开始
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) {
                System.out.print(" -> ");
            } else {
                System.out.println();
            }
            current = current.next;
        }
    }

    // -------------------- 测试主方法 --------------------
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();

        // 测试 1：空链表
        System.out.println("测试 1：空链表");
        System.out.println("链表长度：" + list.getSize()); // 预期：0
        list.printList(); // 预期：（无输出）


        // 测试 2：头插法插入节点
        System.out.println("\n测试 2：头插法插入 1、2、3");
        list.addHead(1); // 链表：dummyHead -> 1
        list.addHead(2); // 链表：dummyHead -> 2 -> 1
        list.addHead(3); // 链表：dummyHead -> 3 -> 2 -> 1
        System.out.println("链表长度：" + list.getSize()); // 预期：3
        list.printList(); // 预期：3 -> 2 -> 1


        // 测试 3：尾插法插入节点
        System.out.println("\n测试 3：尾插法插入 4、5");
        list.addTail(4); // 链表：dummyHead -> 3 -> 2 -> 1 -> 4
        list.addTail(5); // 链表：dummyHead -> 3 -> 2 -> 1 -> 4 -> 5
        System.out.println("链表长度：" + list.getSize()); // 预期：5
        list.printList(); // 预期：3 -> 2 -> 1 -> 4 -> 5


        // 测试 4：指定位置插入节点（index=2）
        System.out.println("\n测试 4：在索引 2 处插入 6");
        list.addAtIndex(2, 6); // 链表：dummyHead -> 3 -> 2 -> 6 -> 1 -> 4 -> 5
        System.out.println("链表长度：" + list.getSize()); // 预期：6
        list.printList(); // 预期：3 -> 2 -> 6 -> 1 -> 4 -> 5


        // 测试 5：按索引查询节点（index=3）
        System.out.println("\n测试 5：查询索引 3 的节点值");
        int value = list.get(3); // 预期：1
        System.out.println("索引 3 的值：" + value);


        // 测试 6：删除指定索引的节点（index=2）
        System.out.println("\n测试 6：删除索引 2 的节点");
        list.deleteAtIndex(2); // 链表：dummyHead -> 3 -> 2 -> 1 -> 4 -> 5
        System.out.println("链表长度：" + list.getSize()); // 预期：5
        list.printList(); // 预期：3 -> 2 -> 1 -> 4 -> 5


        // 测试 7：边界情况（删除头节点，index=0）
        System.out.println("\n测试 7：删除头节点（index=0）");
        list.deleteAtIndex(0); // 链表：dummyHead -> 2 -> 1 -> 4 -> 5
        System.out.println("链表长度：" + list.getSize()); // 预期：4
        list.printList(); // 预期：2 -> 1 -> 4 -> 5


        // 测试 8：边界情况（删除尾节点，index=size-1）
        System.out.println("\n测试 8：删除尾节点（index=3）");
        list.deleteAtIndex(3); // 链表：dummyHead -> 2 -> 1 -> 4
        System.out.println("链表长度：" + list.getSize()); // 预期：3
        list.printList(); // 预期：2 -> 1 -> 4
    }
}